package solver;

import java.util.Random;

public class Commutator444 {
	private static boolean ini = false;
	private String sol;
	private String[] steps = new String[6];

	private static Random r = new Random();

	private class directLayer
	{
		String theMove;
		int theDest;
	};

	private directLayer[][] m_astDirectLayers;
	private directLayer[][] m_astDirectCenterLayers;
	/*
						5
						4	7	7
					3	1	10
							1
		4				2				8				6
		5	3	20		2	12	17		11	9	24		8	6	21
	22	18	14		19	15	23		18	24	20		23	21	17
			12				10				16				14
						9
						13	22	15
					11	16	19
							13
	*/
	private void fill_directLayer(int i, int j, String theMove, int theDest)
	{
		directLayer layer = new directLayer();
		layer.theMove = theMove;
		layer.theDest = theDest;
		m_astDirectLayers[i][j] = layer;
	}

	private void fill_directLayerCenter(int i, int j, String theMove, int theDest)
	{
		directLayer layer = new directLayer();
		layer.theMove = theMove;
		layer.theDest = theDest;
		m_astDirectCenterLayers[i][j] = layer;
	}

	private void init()
	{
		init_centers();
		init_edges();
	}

	private void init_centers()
	{
		int i, j;

		m_astDirectCenterLayers = new directLayer[25][9];

		i = 1;
		j = 0;
		fill_directLayerCenter(i, j++, "MF", 11);
		fill_directLayerCenter(i, j++, "MF2", 22);
		fill_directLayerCenter(i, j++, "MF'", 14);
		fill_directLayerCenter(i, j++, "ML", 15);
		fill_directLayerCenter(i, j++, "ML2", 16);
		fill_directLayerCenter(i, j++, "ML'", 6);
		fill_directLayerCenter(i, j++, "U", 4);
		fill_directLayerCenter(i, j++, "U2", 7);
		fill_directLayerCenter(i, j++, "U'", 10);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "F", 12);
		fill_directLayerCenter(i, j++, "F2", 23);
		fill_directLayerCenter(i, j++, "F'", 15);
		fill_directLayerCenter(i, j++, "ML", 13);
		fill_directLayerCenter(i, j++, "ML2", 17);
		fill_directLayerCenter(i, j++, "ML'", 4);
		fill_directLayerCenter(i, j++, "MU", 5);
		fill_directLayerCenter(i, j++, "MU2", 8);
		fill_directLayerCenter(i, j++, "MU'", 11);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MF", 10);
		fill_directLayerCenter(i, j++, "MF2", 24);
		fill_directLayerCenter(i, j++, "MF'", 13);
		fill_directLayerCenter(i, j++, "L", 14);
		fill_directLayerCenter(i, j++, "L2", 18);
		fill_directLayerCenter(i, j++, "L'", 5);
		fill_directLayerCenter(i, j++, "MU", 6);
		fill_directLayerCenter(i, j++, "MU2", 9);
		fill_directLayerCenter(i, j++, "MU'", 12);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MB", 18);
		fill_directLayerCenter(i, j++, "MB2", 19);
		fill_directLayerCenter(i, j++, "MB'", 9);
		fill_directLayerCenter(i, j++, "U", 7);
		fill_directLayerCenter(i, j++, "U2", 10);
		fill_directLayerCenter(i, j++, "U'", 1);
		fill_directLayerCenter(i, j++, "ML", 2);
		fill_directLayerCenter(i, j++, "ML2", 13);
		fill_directLayerCenter(i, j++, "ML'", 17);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MB", 16);
		fill_directLayerCenter(i, j++, "MB2", 21);
		fill_directLayerCenter(i, j++, "MB'", 7);
		fill_directLayerCenter(i, j++, "MU", 8);
		fill_directLayerCenter(i, j++, "MU2", 11);
		fill_directLayerCenter(i, j++, "MU'", 2);
		fill_directLayerCenter(i, j++, "L", 3);
		fill_directLayerCenter(i, j++, "L2", 14);
		fill_directLayerCenter(i, j++, "L'", 18);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "B", 17);
		fill_directLayerCenter(i, j++, "B2", 20);
		fill_directLayerCenter(i, j++, "B'", 8);
		fill_directLayerCenter(i, j++, "MU", 9);
		fill_directLayerCenter(i, j++, "MU2", 12);
		fill_directLayerCenter(i, j++, "MU'", 3);
		fill_directLayerCenter(i, j++, "ML", 1);
		fill_directLayerCenter(i, j++, "ML2", 15);
		fill_directLayerCenter(i, j++, "ML'", 16);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MB", 5);
		fill_directLayerCenter(i, j++, "MB2", 16);
		fill_directLayerCenter(i, j++, "MB'", 20);
		fill_directLayerCenter(i, j++, "U", 10);
		fill_directLayerCenter(i, j++, "U2", 1);
		fill_directLayerCenter(i, j++, "U'", 4);
		fill_directLayerCenter(i, j++, "MR", 21);
		fill_directLayerCenter(i, j++, "MR2", 22);
		fill_directLayerCenter(i, j++, "MR'", 12);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "B", 6);
		fill_directLayerCenter(i, j++, "B2", 17);
		fill_directLayerCenter(i, j++, "B'", 21);
		fill_directLayerCenter(i, j++, "MU", 11);
		fill_directLayerCenter(i, j++, "MU2", 2);
		fill_directLayerCenter(i, j++, "MU'", 5);
		fill_directLayerCenter(i, j++, "MR", 19);
		fill_directLayerCenter(i, j++, "MR2", 23);
		fill_directLayerCenter(i, j++, "MR'", 10);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MB", 4);
		fill_directLayerCenter(i, j++, "MB2", 18);
		fill_directLayerCenter(i, j++, "MB'", 19);
		fill_directLayerCenter(i, j++, "MU", 12);
		fill_directLayerCenter(i, j++, "MU2", 3);
		fill_directLayerCenter(i, j++, "MU'", 6);
		fill_directLayerCenter(i, j++, "R", 20);
		fill_directLayerCenter(i, j++, "R2", 24);
		fill_directLayerCenter(i, j++, "R'", 11);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MF", 24);
		fill_directLayerCenter(i, j++, "MF2", 13);
		fill_directLayerCenter(i, j++, "MF'", 3);
		fill_directLayerCenter(i, j++, "U", 1);
		fill_directLayerCenter(i, j++, "U2", 4);
		fill_directLayerCenter(i, j++, "U'", 7);
		fill_directLayerCenter(i, j++, "MR", 8);
		fill_directLayerCenter(i, j++, "MR2", 19);
		fill_directLayerCenter(i, j++, "MR'", 23);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MF", 22);
		fill_directLayerCenter(i, j++, "MF2", 14);
		fill_directLayerCenter(i, j++, "MF'", 1);
		fill_directLayerCenter(i, j++, "MU", 2);
		fill_directLayerCenter(i, j++, "MU2", 5);
		fill_directLayerCenter(i, j++, "MU'", 8);
		fill_directLayerCenter(i, j++, "R", 9);
		fill_directLayerCenter(i, j++, "R2", 20);
		fill_directLayerCenter(i, j++, "R'", 24);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "F", 23);
		fill_directLayerCenter(i, j++, "F2", 15);
		fill_directLayerCenter(i, j++, "F'", 2);
		fill_directLayerCenter(i, j++, "MU", 3);
		fill_directLayerCenter(i, j++, "MU2", 6);
		fill_directLayerCenter(i, j++, "MU'", 9);
		fill_directLayerCenter(i, j++, "MR", 7);
		fill_directLayerCenter(i, j++, "MR2", 21);
		fill_directLayerCenter(i, j++, "MR'", 22);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "ML", 17);
		fill_directLayerCenter(i, j++, "ML2", 4);
		fill_directLayerCenter(i, j++, "ML'", 2);
		fill_directLayerCenter(i, j++, "MF", 3);
		fill_directLayerCenter(i, j++, "MF2", 10);
		fill_directLayerCenter(i, j++, "MF'", 24);
		fill_directLayerCenter(i, j++, "D", 22);
		fill_directLayerCenter(i, j++, "D2", 19);
		fill_directLayerCenter(i, j++, "D'", 16);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "L", 18);
		fill_directLayerCenter(i, j++, "L2", 5);
		fill_directLayerCenter(i, j++, "L'", 3);
		fill_directLayerCenter(i, j++, "MF", 1);
		fill_directLayerCenter(i, j++, "MF2", 11);
		fill_directLayerCenter(i, j++, "MF'", 22);
		fill_directLayerCenter(i, j++, "MD", 23);
		fill_directLayerCenter(i, j++, "MD2", 20);
		fill_directLayerCenter(i, j++, "MD'", 17);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "ML", 16);
		fill_directLayerCenter(i, j++, "ML2", 6);
		fill_directLayerCenter(i, j++, "ML'", 1);
		fill_directLayerCenter(i, j++, "F", 2);
		fill_directLayerCenter(i, j++, "F2", 12);
		fill_directLayerCenter(i, j++, "F'", 23);
		fill_directLayerCenter(i, j++, "MD", 24);
		fill_directLayerCenter(i, j++, "MD2", 21);
		fill_directLayerCenter(i, j++, "MD'", 18);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "ML", 6);
		fill_directLayerCenter(i, j++, "ML2", 1);
		fill_directLayerCenter(i, j++, "ML'", 15);
		fill_directLayerCenter(i, j++, "MB", 21);
		fill_directLayerCenter(i, j++, "MB2", 7);
		fill_directLayerCenter(i, j++, "MB'", 5);
		fill_directLayerCenter(i, j++, "D", 13);
		fill_directLayerCenter(i, j++, "D2", 22);
		fill_directLayerCenter(i, j++, "D'", 19);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "ML", 4);
		fill_directLayerCenter(i, j++, "ML2", 2);
		fill_directLayerCenter(i, j++, "ML'", 13);
		fill_directLayerCenter(i, j++, "B", 20);
		fill_directLayerCenter(i, j++, "B2", 8);
		fill_directLayerCenter(i, j++, "B'", 6);
		fill_directLayerCenter(i, j++, "MD", 14);
		fill_directLayerCenter(i, j++, "MD2", 23);
		fill_directLayerCenter(i, j++, "MD'", 20);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "L", 5);
		fill_directLayerCenter(i, j++, "L2", 3);
		fill_directLayerCenter(i, j++, "L'", 14);
		fill_directLayerCenter(i, j++, "MB", 19);
		fill_directLayerCenter(i, j++, "MB2", 9);
		fill_directLayerCenter(i, j++, "MB'", 4);
		fill_directLayerCenter(i, j++, "MD", 15);
		fill_directLayerCenter(i, j++, "MD2", 24);
		fill_directLayerCenter(i, j++, "MD'", 21);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MB", 9);
		fill_directLayerCenter(i, j++, "MB2", 4);
		fill_directLayerCenter(i, j++, "MB'", 18);
		fill_directLayerCenter(i, j++, "MR", 23);
		fill_directLayerCenter(i, j++, "MR2", 10);
		fill_directLayerCenter(i, j++, "MR'", 8);
		fill_directLayerCenter(i, j++, "D", 16);
		fill_directLayerCenter(i, j++, "D2", 13);
		fill_directLayerCenter(i, j++, "D'", 22);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MB", 7);
		fill_directLayerCenter(i, j++, "MB2", 5);
		fill_directLayerCenter(i, j++, "MB'", 16);
		fill_directLayerCenter(i, j++, "R", 24);
		fill_directLayerCenter(i, j++, "R2", 11);
		fill_directLayerCenter(i, j++, "R'", 9);
		fill_directLayerCenter(i, j++, "MD", 17);
		fill_directLayerCenter(i, j++, "MD2", 14);
		fill_directLayerCenter(i, j++, "MD'", 24);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "B", 8);
		fill_directLayerCenter(i, j++, "B2", 6);
		fill_directLayerCenter(i, j++, "B'", 17);
		fill_directLayerCenter(i, j++, "MR", 22);
		fill_directLayerCenter(i, j++, "MR2", 12);
		fill_directLayerCenter(i, j++, "MR'", 7);
		fill_directLayerCenter(i, j++, "MD", 18);
		fill_directLayerCenter(i, j++, "MD2", 15);
		fill_directLayerCenter(i, j++, "MD'", 24);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MF", 14);
		fill_directLayerCenter(i, j++, "MF2", 1);
		fill_directLayerCenter(i, j++, "MF'", 11);
		fill_directLayerCenter(i, j++, "MR", 12);
		fill_directLayerCenter(i, j++, "MR2", 7);
		fill_directLayerCenter(i, j++, "MR'", 21);
		fill_directLayerCenter(i, j++, "D", 19);
		fill_directLayerCenter(i, j++, "D2", 16);
		fill_directLayerCenter(i, j++, "D'", 13);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "F", 15);
		fill_directLayerCenter(i, j++, "F2", 2);
		fill_directLayerCenter(i, j++, "F'", 12);
		fill_directLayerCenter(i, j++, "MR", 10);
		fill_directLayerCenter(i, j++, "MR2", 8);
		fill_directLayerCenter(i, j++, "MR'", 19);
		fill_directLayerCenter(i, j++, "MD", 20);
		fill_directLayerCenter(i, j++, "MD2", 17);
		fill_directLayerCenter(i, j++, "MD'", 14);

		i++;
		j = 0;
		fill_directLayerCenter(i, j++, "MF", 13);
		fill_directLayerCenter(i, j++, "MF2", 3);
		fill_directLayerCenter(i, j++, "MF'", 10);
		fill_directLayerCenter(i, j++, "R", 11);
		fill_directLayerCenter(i, j++, "R2", 9);
		fill_directLayerCenter(i, j++, "R'", 20);
		fill_directLayerCenter(i, j++, "MD", 21);
		fill_directLayerCenter(i, j++, "MD2", 18);
		fill_directLayerCenter(i, j++, "MD'", 15);
	}

	private void init_edges()
	{
		int i, j;

		m_astDirectLayers = new directLayer[25][9];

		i = 1;
		j = 0;
		fill_directLayer(i, j++, "U", 3);
		fill_directLayer(i, j++, "U2", 5);
		fill_directLayer(i, j++, "U'", 7);
		fill_directLayer(i, j++, "F", 18);
		fill_directLayer(i, j++, "F2", 9);
		fill_directLayer(i, j++, "F'", 20);
		fill_directLayer(i, j++, "MR'", 10);
		fill_directLayer(i, j++, "MR2", 13);
		fill_directLayer(i, j++, "MR'", 6);

		i++;
		j = 0;
		fill_directLayer(i, j++, "U", 4);
		fill_directLayer(i, j++, "U2", 6);
		fill_directLayer(i, j++, "U'", 8);
		fill_directLayer(i, j++, "F", 17);
		fill_directLayer(i, j++, "F2", 10);
		fill_directLayer(i, j++, "F'", 19);
		fill_directLayer(i, j++, "ML", 9);
		fill_directLayer(i, j++, "ML2", 14);
		fill_directLayer(i, j++, "ML'", 5);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 19);
		fill_directLayer(i, j++, "L2", 11);
		fill_directLayer(i, j++, "L'", 21);
		fill_directLayer(i, j++, "U", 5);
		fill_directLayer(i, j++, "U2", 7);
		fill_directLayer(i, j++, "U'", 1);
		fill_directLayer(i, j++, "MF", 8);
		fill_directLayer(i, j++, "MF2", 15);
		fill_directLayer(i, j++, "MF'", 12);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 20);
		fill_directLayer(i, j++, "L2", 12);
		fill_directLayer(i, j++, "L'", 22);
		fill_directLayer(i, j++, "U", 6);
		fill_directLayer(i, j++, "U2", 8);
		fill_directLayer(i, j++, "U'", 2);
		fill_directLayer(i, j++, "MF", 7);
		fill_directLayer(i, j++, "MF2", 16);
		fill_directLayer(i, j++, "MF'", 11);

		i++;
		j = 0;
		fill_directLayer(i, j++, "B", 22);
		fill_directLayer(i, j++, "B2", 13);
		fill_directLayer(i, j++, "B'", 24);
		fill_directLayer(i, j++, "U", 7);
		fill_directLayer(i, j++, "U2", 1);
		fill_directLayer(i, j++, "U'", 3);
		fill_directLayer(i, j++, "ML", 2);
		fill_directLayer(i, j++, "ML2", 9);
		fill_directLayer(i, j++, "ML'", 14);

		i++;
		j = 0;
		fill_directLayer(i, j++, "B", 21);
		fill_directLayer(i, j++, "B2", 14);
		fill_directLayer(i, j++, "B'", 23);
		fill_directLayer(i, j++, "U", 8);
		fill_directLayer(i, j++, "U2", 2);
		fill_directLayer(i, j++, "U'", 4);
		fill_directLayer(i, j++, "MR'", 1);
		fill_directLayer(i, j++, "MR2", 10);
		fill_directLayer(i, j++, "MR", 13);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 23);
		fill_directLayer(i, j++, "R2", 15);
		fill_directLayer(i, j++, "R'", 17);
		fill_directLayer(i, j++, "U", 1);
		fill_directLayer(i, j++, "U2", 3);
		fill_directLayer(i, j++, "U'", 5);
		fill_directLayer(i, j++, "MB'", 16);
		fill_directLayer(i, j++, "MB2", 11);
		fill_directLayer(i, j++, "MB", 4);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 24);
		fill_directLayer(i, j++, "R2", 16);
		fill_directLayer(i, j++, "R'", 18);
		fill_directLayer(i, j++, "U", 2);
		fill_directLayer(i, j++, "U2", 4);
		fill_directLayer(i, j++, "U'", 6);
		fill_directLayer(i, j++, "MF", 15);
		fill_directLayer(i, j++, "MF2", 12);
		fill_directLayer(i, j++, "MF'", 3);

		i++;
		j = 0;
		fill_directLayer(i, j++, "F", 20);
		fill_directLayer(i, j++, "F2", 1);
		fill_directLayer(i, j++, "F'", 18);
		fill_directLayer(i, j++, "D", 15);
		fill_directLayer(i, j++, "D2", 13);
		fill_directLayer(i, j++, "D'", 11);
		fill_directLayer(i, j++, "ML", 14);
		fill_directLayer(i, j++, "ML2", 5);
		fill_directLayer(i, j++, "ML'", 2);

		i++;
		j = 0;
		fill_directLayer(i, j++, "F", 19);
		fill_directLayer(i, j++, "F2", 2);
		fill_directLayer(i, j++, "F'", 17);
		fill_directLayer(i, j++, "D", 16);
		fill_directLayer(i, j++, "D2", 14);
		fill_directLayer(i, j++, "D'", 12);
		fill_directLayer(i, j++, "MR'", 13);
		fill_directLayer(i, j++, "MR2", 6);
		fill_directLayer(i, j++, "MR", 1);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 21);
		fill_directLayer(i, j++, "L2", 3);
		fill_directLayer(i, j++, "L'", 19);
		fill_directLayer(i, j++, "D", 9);
		fill_directLayer(i, j++, "D2", 15);
		fill_directLayer(i, j++, "D'", 13);
		fill_directLayer(i, j++, "MB'", 4);
		fill_directLayer(i, j++, "MB2", 7);
		fill_directLayer(i, j++, "MB", 16);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 22);
		fill_directLayer(i, j++, "L2", 4);
		fill_directLayer(i, j++, "L'", 20);
		fill_directLayer(i, j++, "D", 10);
		fill_directLayer(i, j++, "D2", 16);
		fill_directLayer(i, j++, "D'", 14);
		fill_directLayer(i, j++, "MF", 3);
		fill_directLayer(i, j++, "MF2", 8);
		fill_directLayer(i, j++, "MF'", 15);

		i++;
		j = 0;
		fill_directLayer(i, j++, "B", 24);
		fill_directLayer(i, j++, "B2", 5);
		fill_directLayer(i, j++, "B'", 22);
		fill_directLayer(i, j++, "D", 11);
		fill_directLayer(i, j++, "D2", 9);
		fill_directLayer(i, j++, "D'", 15);
		fill_directLayer(i, j++, "MR'", 6);
		fill_directLayer(i, j++, "MR2", 1);
		fill_directLayer(i, j++, "MR", 10);

		i++;
		j = 0;
		fill_directLayer(i, j++, "B", 23);
		fill_directLayer(i, j++, "B2", 6);
		fill_directLayer(i, j++, "B'", 21);
		fill_directLayer(i, j++, "D", 12);
		fill_directLayer(i, j++, "D2", 10);
		fill_directLayer(i, j++, "D'", 16);
		fill_directLayer(i, j++, "ML", 5);
		fill_directLayer(i, j++, "ML2", 2);
		fill_directLayer(i, j++, "ML'", 9);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 17);
		fill_directLayer(i, j++, "R2", 7);
		fill_directLayer(i, j++, "R'", 23);
		fill_directLayer(i, j++, "D", 13);
		fill_directLayer(i, j++, "D2", 11);
		fill_directLayer(i, j++, "D'", 9);
		fill_directLayer(i, j++, "MF", 12);
		fill_directLayer(i, j++, "MF2", 3);
		fill_directLayer(i, j++, "MF'", 8);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 18);
		fill_directLayer(i, j++, "R2", 8);
		fill_directLayer(i, j++, "R'", 24);
		fill_directLayer(i, j++, "D", 14);
		fill_directLayer(i, j++, "D2", 12);
		fill_directLayer(i, j++, "D'", 10);
		fill_directLayer(i, j++, "MB'", 11);
		fill_directLayer(i, j++, "MB2", 4);
		fill_directLayer(i, j++, "MB", 7);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 7);
		fill_directLayer(i, j++, "R2", 23);
		fill_directLayer(i, j++, "R'", 15);
		fill_directLayer(i, j++, "MU'", 24);
		fill_directLayer(i, j++, "MU2", 21);
		fill_directLayer(i, j++, "MU", 20);
		fill_directLayer(i, j++, "F", 10);
		fill_directLayer(i, j++, "F2", 19);
		fill_directLayer(i, j++, "F'", 2);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 8);
		fill_directLayer(i, j++, "R2", 24);
		fill_directLayer(i, j++, "R'", 16);
		fill_directLayer(i, j++, "MD", 23);
		fill_directLayer(i, j++, "MD2", 22);
		fill_directLayer(i, j++, "MD'", 19);
		fill_directLayer(i, j++, "F", 9);
		fill_directLayer(i, j++, "F2", 20);
		fill_directLayer(i, j++, "F'", 1);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 11);
		fill_directLayer(i, j++, "L2", 21);
		fill_directLayer(i, j++, "L'", 3);
		fill_directLayer(i, j++, "MD", 18);
		fill_directLayer(i, j++, "MD2", 23);
		fill_directLayer(i, j++, "MD'", 22);
		fill_directLayer(i, j++, "F", 2);
		fill_directLayer(i, j++, "F2", 17);
		fill_directLayer(i, j++, "F'", 10);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 12);
		fill_directLayer(i, j++, "L2", 22);
		fill_directLayer(i, j++, "L'", 4);
		fill_directLayer(i, j++, "MU'", 17);
		fill_directLayer(i, j++, "MU2", 24);
		fill_directLayer(i, j++, "MU", 21);
		fill_directLayer(i, j++, "F", 1);
		fill_directLayer(i, j++, "F2", 18);
		fill_directLayer(i, j++, "F'", 9);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 3);
		fill_directLayer(i, j++, "L2", 19);
		fill_directLayer(i, j++, "L'", 11);
		fill_directLayer(i, j++, "MU'", 20);
		fill_directLayer(i, j++, "MU2", 17);
		fill_directLayer(i, j++, "MU", 24);
		fill_directLayer(i, j++, "B", 14);
		fill_directLayer(i, j++, "B2", 23);
		fill_directLayer(i, j++, "B'", 6);

		i++;
		j = 0;
		fill_directLayer(i, j++, "L", 4);
		fill_directLayer(i, j++, "L2", 20);
		fill_directLayer(i, j++, "L'", 12);
		fill_directLayer(i, j++, "MD", 19);
		fill_directLayer(i, j++, "MD2", 18);
		fill_directLayer(i, j++, "MD'", 23);
		fill_directLayer(i, j++, "B", 13);
		fill_directLayer(i, j++, "B2", 24);
		fill_directLayer(i, j++, "B'", 5);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 15);
		fill_directLayer(i, j++, "R2", 17);
		fill_directLayer(i, j++, "R'", 7);
		fill_directLayer(i, j++, "MD", 22);
		fill_directLayer(i, j++, "MD2", 19);
		fill_directLayer(i, j++, "MD'", 18);
		fill_directLayer(i, j++, "B", 6);
		fill_directLayer(i, j++, "B2", 21);
		fill_directLayer(i, j++, "B'", 14);

		i++;
		j = 0;
		fill_directLayer(i, j++, "R", 16);
		fill_directLayer(i, j++, "R2", 18);
		fill_directLayer(i, j++, "R'", 8);
		fill_directLayer(i, j++, "MU'", 21);
		fill_directLayer(i, j++, "MD2", 20);
		fill_directLayer(i, j++, "MU", 17);
		fill_directLayer(i, j++, "B", 5);
		fill_directLayer(i, j++, "B2", 22);
		fill_directLayer(i, j++, "B'", 13);
	}

	public Commutator444() {
		if(!ini) {
			init();
			ini = true;
		}
	}

	String[] calc_switch_layers(String layer)
	{
		String[] result = new String[3];

		if ( 'M' == layer.charAt(0) )
		{
			switch ( layer.charAt(1) )
			{
				case 'R':
					result[0] = "R";
					result[1] = "L";
					result[2] = "L";
					break;

				case 'L':
					result[0] = "R";
					result[1] = "L";
					result[2] = "R";
					break;

				case 'U':
					result[0] = "U";
					result[1] = "D";
					result[2] = "D";
					break;

				case 'D':
					result[0] = "U";
					result[1] = "U";
					result[2] = "D";
					break;

				case 'F':
					result[0] = "F";
					result[1] = "B";
					result[2] = "B";
					break;

				case 'B':
					result[0] = "F";
					result[1] = "F";
					result[2] = "B";
					break;

				default:
					break;
			}
		}
		else {
			switch (layer.charAt(0)) {
				case 'R':
					result[0] = "MR";
					result[1] = "ML";
					result[2] = "ML";
					break;

				case 'L':
					result[0] = "MR";
					result[1] = "ML";
					result[2] = "MR";
					break;

				case 'U':
					result[0] = "MU";
					result[1] = "MD";
					result[2] = "MD";
					break;

				case 'D':
					result[0] = "MD";
					result[1] = "MU";
					result[2] = "MU";
					break;

				case 'F':
					result[0] = "MF";
					result[1] = "MB";
					result[2] = "MB";
					break;

				case 'B':
					result[0] = "MB";
					result[1] = "MF";
					result[2] = "MF";
					break;

				default:
					break;
			}
		}

		return result;
	}

	String[] calc_switch_layers_center(String layer)
	{
		String[] result = new String[3];

		if ( 'M' == layer.charAt(0) )
		{
			switch ( layer.charAt(1) )
			{
				case 'R':
					result[0] = "R";
					result[1] = "ML";
					result[2] = "L";
					break;

				case 'L':
					result[0] = "MR";
					result[1] = "L";
					result[2] = "R";
					break;

				case 'U':
					result[0] = "U";
					result[1] = "MD";
					result[2] = "D";
					break;

				case 'D':
					result[0] = "MU";
					result[1] = "U";
					result[2] = "D";
					break;

				case 'F':
					result[0] = "F";
					result[1] = "MB";
					result[2] = "B";
					break;

				case 'B':
					result[0] = "MF";
					result[1] = "F";
					result[2] = "B";
					break;

				default:
					break;
			}
		}
		else {
			switch (layer.charAt(0)) {
				case 'R':
					result[0] = "MR";
					result[1] = "ML";
					result[2] = "ML";
					break;

				case 'L':
					result[0] = "MR";
					result[1] = "ML";
					result[2] = "MR";
					break;

				case 'U':
					result[0] = "MU";
					result[1] = "MD";
					result[2] = "MD";
					break;

				case 'D':
					result[0] = "MD";
					result[1] = "MU";
					result[2] = "MU";
					break;

				case 'F':
					result[0] = "MF";
					result[1] = "MB";
					result[2] = "MB";
					break;

				case 'B':
					result[0] = "MB";
					result[1] = "MF";
					result[2] = "MF";
					break;

				default:
					break;
			}
		}

		return result;
	}

	String reverse_move(String themove)
	{
		String[] temp = themove.split(" ");
		String result = "";

		for (int i = temp.length - 1; i >= 0; i--)
		{
			if ( temp[i].contains("2") )
			{
				result += " " + temp[i];
			}
			else if ( !temp[i].contains("'") )
			{
				result += " " + (temp[i] + "'");
			}
			else
			{
				result += " " + temp[i].substring(0, temp[i].length()-1);
			}
		}

		return result.substring(1);
	}

	public String scramble(int type) {
		try {
			if ( 0 == type )
			{
				return scramble_edge();
			}

			return scramble_center();
		}
		catch (Exception e)
		{
			System.out.println(e.toString());
		}

		steps[0] = "null";
		steps[1] = "null";
		steps[2] = "null";
		steps[3] = "null";
		steps[4] = "null";
		steps[5] = "null";

		return "";
	}

	private String scramble_center() {
		int aiFaces[] = new int[3];
		String pcDirectLayerMove = null;
		int iSecondFace, iTemp, iSwitchDirectFace, iDirectOtherFace, iSwitchOthreFace, i, j, k, iSwitchLayer, iCount, iCount2, iCount3;
		String[] acSwitchLayers = new String[3];
		String acDirectToSwitch = null;
		String setupMove = null;

		aiFaces[0] = r.nextInt(24) + 1; //定为缓冲

		iSecondFace = r.nextInt(9);
		aiFaces[1] = m_astDirectCenterLayers[aiFaces[0]][iSecondFace].theDest;
		pcDirectLayerMove = m_astDirectCenterLayers[aiFaces[0]][iSecondFace].theMove;

		iTemp = r.nextInt(2);
		iSwitchDirectFace = aiFaces[iTemp];
		iDirectOtherFace = aiFaces[1 - iTemp];
		if ( 0 == iTemp ) {
			pcDirectLayerMove = reverse_move(pcDirectLayerMove);
		}
		//System.out.println(String.format("==============direct layer %d %d, move %s, switch direct %d, other %d\r\n", aiFaces[0], aiFaces[1], pcDirectLayerMove, iSwitchDirectFace, iDirectOtherFace));

		acSwitchLayers = calc_switch_layers_center(pcDirectLayerMove);
		iSwitchLayer = r.nextInt(3);
		//System.out.println("====switch layer " + acSwitchLayers[iSwitchLayer]);

		iSwitchOthreFace = 0;
		for ( i = r.nextInt(9), iCount = 0; 0 == iSwitchOthreFace && iCount < 9; iCount++, i++ )
		{
			if ( 9 <= i ) i = 0;
			if ( 'M' == pcDirectLayerMove.charAt(0) && 'M' == m_astDirectCenterLayers[iSwitchDirectFace][i].theMove.charAt(0) )
			{
				if ( pcDirectLayerMove.charAt(1) == m_astDirectCenterLayers[iSwitchDirectFace][i].theMove.charAt(1) ) {
					continue;
				}
			}
			else if ( pcDirectLayerMove.charAt(0) == m_astDirectCenterLayers[iSwitchDirectFace][i].theMove.charAt(0) )
			{
				continue;
			}

			if ( '2' == m_astDirectCenterLayers[iSwitchDirectFace][i].theMove.charAt(m_astDirectCenterLayers[iSwitchDirectFace][i].theMove.length() - 1) )
			{
				continue;
			}

			iTemp = m_astDirectCenterLayers[iSwitchDirectFace][i].theDest;
			for ( j = r.nextInt(9), iCount2 = 0; iCount2 < 9; iCount2++, j++ )
			{
				if ( 9 <= j ) j = 0;
				if ( 'M' == acSwitchLayers[iSwitchLayer].charAt(0) && 'M' == m_astDirectCenterLayers[iTemp][j].theMove.charAt(0) ) {
					if (acSwitchLayers[iSwitchLayer].charAt(1) == m_astDirectCenterLayers[iTemp][j].theMove.charAt(1)) {
						iSwitchOthreFace = iTemp;
						acDirectToSwitch = reverse_move(m_astDirectCenterLayers[iSwitchDirectFace][i].theMove);
						break;
					}
				}
				else if ( m_astDirectCenterLayers[iTemp][j].theMove.charAt(0) == acSwitchLayers[iSwitchLayer].charAt(0) )
				{
					iSwitchOthreFace = iTemp;
					acDirectToSwitch = reverse_move(m_astDirectCenterLayers[iSwitchDirectFace][i].theMove);
					break;
				}
			}
		}

		//System.out.println(String.format("===========the othre face %d, switch layer %s, to layer %s\r\n", iSwitchOthreFace, acSwitchLayers[iSwitchLayer], acDirectToSwitch));

		for ( i = r.nextInt(9), iCount = 0; iCount < 9; iCount++, i++)
		{
			if ( 9 <= i ) i = 0;
			if ( 'M' == acSwitchLayers[iSwitchLayer].charAt(0) && 'M' == m_astDirectCenterLayers[iSwitchOthreFace][i].theMove.charAt(0) )
			{
				if ( acSwitchLayers[iSwitchLayer].charAt(1) != m_astDirectCenterLayers[iSwitchOthreFace][i].theMove.charAt(1) ) {
					continue;
				}
			}
			else if ( acSwitchLayers[iSwitchLayer].charAt(0) != m_astDirectCenterLayers[iSwitchOthreFace][i].theMove.charAt(0) )
			{
				continue;
			}

			iTemp = m_astDirectCenterLayers[iSwitchOthreFace][i].theDest;
			for ( j = r.nextInt(9), iCount2 = 0; iCount2 < 9; iCount2++, j++ ) {
				if ( 9 <= j ) j = 0;
				for ( k = r.nextInt(9), iCount3 = 0; iCount3 < 9; iCount3++, k++ )
				{
					if ( 9 <= k ) k = 0;
					if ( 'M' == acDirectToSwitch.charAt(0) && 'M' == m_astDirectCenterLayers[m_astDirectCenterLayers[iTemp][j].theDest][k].theMove.charAt(0) )
					{
						if ( acDirectToSwitch.charAt(1) == m_astDirectCenterLayers[m_astDirectCenterLayers[iTemp][j].theDest][k].theMove.charAt(1) ) {
							break;
						}
					}
					else if ( m_astDirectCenterLayers[m_astDirectCenterLayers[iTemp][j].theDest][k].theMove.charAt(0) == acDirectToSwitch.charAt(0) )
					{
						break;
					}
				}

				if ( 9 > iCount3 )
				{
					continue;
				}

				setupMove = m_astDirectCenterLayers[iSwitchOthreFace][i].theMove;
				break;
			}

			if ( 9 > iCount2 )
			{
				break;
			}
		}

		setupMove = reverse_move(setupMove);
		//System.out.println("====setup " + setupMove);
		sol = setupMove + " " + pcDirectLayerMove + " " + reverse_move(acDirectToSwitch) + " " + reverse_move(setupMove) + " " + acDirectToSwitch
				+ " " + reverse_move(pcDirectLayerMove) + " " + reverse_move(acDirectToSwitch) + " " + setupMove + " " + acDirectToSwitch + " " + reverse_move(setupMove);
		//System.out.println("====sol " + sol);
		//System.out.println("====scr " + reverse_move(sol));

		steps[0] = setupMove;
		steps[1] = pcDirectLayerMove;
		steps[2] = reverse_move(acDirectToSwitch) + " " + reverse_move(setupMove) + " " + acDirectToSwitch;
		steps[3] = reverse_move(pcDirectLayerMove);
		steps[4] = reverse_move(acDirectToSwitch) + " " + setupMove + " " + acDirectToSwitch;
		steps[5] = reverse_move(setupMove);

		return reverse_move(sol);
	}

	private String scramble_edge() {
		int aiFaces[] = new int[3];
		String pcDirectLayerMove = null;
		int iSecondFace, iTemp, iSwitchDirectFace, iDirectOtherFace, iSwitchOthreFace, i, j, k, iSwitchLayer, iCount, iCount2, iCount3;
		String[] acSwitchLayers = new String[3];
		String acDirectToSwitch = null;
		String setupMove = null;

		aiFaces[0] = r.nextInt(24) + 1; //定为缓冲

		iSecondFace = r.nextInt(9);
		aiFaces[1] = m_astDirectLayers[aiFaces[0]][iSecondFace].theDest;
		pcDirectLayerMove = m_astDirectLayers[aiFaces[0]][iSecondFace].theMove;

		iTemp = r.nextInt(2);
		iSwitchDirectFace = aiFaces[iTemp];
		iDirectOtherFace = aiFaces[1 - iTemp];
		if ( 0 == iTemp ) {
			pcDirectLayerMove = reverse_move(pcDirectLayerMove);
		}
		//System.out.println(String.format("==============direct layer %d %d, move %s, switch direct %d, other %d\r\n", aiFaces[0], aiFaces[1], pcDirectLayerMove, iSwitchDirectFace, iDirectOtherFace));

		acSwitchLayers = calc_switch_layers(pcDirectLayerMove);
		iSwitchLayer = r.nextInt(3);
		//System.out.println("====switch layer " + acSwitchLayers[iSwitchLayer]);

		iSwitchOthreFace = 0;
		for ( i = r.nextInt(9), iCount = 0; 0 == iSwitchOthreFace && iCount < 9; iCount++ , i++)
		{
			if ( 9 <= i ) i = 0;
			if ( 'M' == pcDirectLayerMove.charAt(0) && 'M' == m_astDirectLayers[iSwitchDirectFace][i].theMove.charAt(0) )
			{
				if ( pcDirectLayerMove.charAt(1) == m_astDirectLayers[iSwitchDirectFace][i].theMove.charAt(1) ) {
					continue;
				}
			}
			else if ( pcDirectLayerMove.charAt(0) == m_astDirectLayers[iSwitchDirectFace][i].theMove.charAt(0) )
			{
				continue;
			}

			if ( '2' == m_astDirectLayers[iSwitchDirectFace][i].theMove.charAt(m_astDirectLayers[iSwitchDirectFace][i].theMove.length() - 1) )
			{
				continue;
			}

			iTemp = m_astDirectLayers[iSwitchDirectFace][i].theDest;
			for ( j = r.nextInt(9), iCount2 = 0; iCount2 < 9; iCount2++, j++ )
			{
				if ( 9 <= j ) j = 0;
				if ( 'M' == acSwitchLayers[iSwitchLayer].charAt(0) && 'M' == m_astDirectLayers[iTemp][j].theMove.charAt(0) ) {
					if (acSwitchLayers[iSwitchLayer].charAt(1) == m_astDirectLayers[iTemp][j].theMove.charAt(1)) {
						iSwitchOthreFace = iTemp;
						acDirectToSwitch = reverse_move(m_astDirectLayers[iSwitchDirectFace][i].theMove);
						break;
					}
				}
				else if ( m_astDirectLayers[iTemp][j].theMove.charAt(0) == acSwitchLayers[iSwitchLayer].charAt(0) )
				{
					iSwitchOthreFace = iTemp;
					acDirectToSwitch = reverse_move(m_astDirectLayers[iSwitchDirectFace][i].theMove);
					break;
				}
			}
		}

		//System.out.println(String.format("===========the othre face %d, switch layer %s, to layer %c\r\n", iSwitchOthreFace, acSwitchLayers[iSwitchLayer], acDirectToSwitch.charAt(0)));

		for ( i = r.nextInt(9), iCount = 0; iCount < 9; iCount++, i++)
		{
			if ( 9 <= i ) i = 0;
			if ( 'M' == acSwitchLayers[iSwitchLayer].charAt(0) && 'M' == m_astDirectLayers[iSwitchOthreFace][i].theMove.charAt(0) )
			{
				if ( acSwitchLayers[iSwitchLayer].charAt(1) != m_astDirectLayers[iSwitchOthreFace][i].theMove.charAt(1) ) {
					continue;
				}
			}
			else if ( acSwitchLayers[iSwitchLayer].charAt(0) != m_astDirectLayers[iSwitchOthreFace][i].theMove.charAt(0) )
			{
				continue;
			}

			iTemp = m_astDirectLayers[iSwitchOthreFace][i].theDest;
			for ( j = r.nextInt(9), iCount2 = 0; iCount2 < 9; iCount2++, j++ ) {
				if ( 9 <= j ) j = 0;
				for ( k = r.nextInt(9), iCount3 = 0; iCount3 < 9; iCount3++, k++ )
				{
					if ( 9 <= k ) k = 0;
					if ( 'M' == acDirectToSwitch.charAt(0) && 'M' == m_astDirectLayers[m_astDirectCenterLayers[iTemp][j].theDest][k].theMove.charAt(0) )
					{
						if ( acDirectToSwitch.charAt(1) == m_astDirectLayers[m_astDirectLayers[iTemp][j].theDest][k].theMove.charAt(1) ) {
							break;
						}
					}
					else if ( m_astDirectLayers[m_astDirectLayers[iTemp][j].theDest][k].theMove.charAt(0) == acDirectToSwitch.charAt(0) )
					{
						break;
					}
				}

				if ( 9 > iCount3 )
				{
					continue;
				}

				setupMove = m_astDirectLayers[iSwitchOthreFace][i].theMove;
				break;
			}

			if ( 9 > iCount2 )
			{
				break;
			}
		}

		//System.out.println("====setup " + setupMove);
		sol = setupMove + " " + pcDirectLayerMove + " " + reverse_move(acDirectToSwitch) + " " + reverse_move(setupMove) + " " + acDirectToSwitch
				+ " " + reverse_move(pcDirectLayerMove) + " " + reverse_move(acDirectToSwitch) + " " + setupMove + " " + acDirectToSwitch + " " + reverse_move(setupMove);
		//System.out.println("====sol " + sol);
		//System.out.println("====scr " + reverse_move(sol));

		steps[0] = setupMove;
		steps[1] = pcDirectLayerMove;
		steps[2] = reverse_move(acDirectToSwitch) + " " + reverse_move(setupMove) + " " + acDirectToSwitch;
		steps[3] = reverse_move(pcDirectLayerMove);
		steps[4] = reverse_move(acDirectToSwitch) + " " + setupMove + " " + acDirectToSwitch;
		steps[5] = reverse_move(setupMove);

		return reverse_move(sol);
	}

	public String getResolve(String scr)
	{
		return "Setup: " + steps[0] + "\nA: " + steps[1] + "\nB: " + steps[2] + "\nA': " + steps[3] + "\nB': " + steps[4] + "\nReverse: " + steps[5];
	}
}
